#ifndef __CORE_COMMON_HASH_MAP_H_INCLUDE__
#define __CORE_COMMON_HASH_MAP_H_INCLUDE__

#include <stdio.h>
#include <assert.h>

namespace core{ namespace common
{
	template<class K, class T>
	class HashNode
	{
	public:
		K key_;
		T value_;
		HashNode<K, T> *child_;
		HashNode<K, T> *previous_;
		HashNode<K, T> *next_;

		HashNode( const K &key, const T &value ) : 
			key_(key),
			value_(value),
			child_(NULL),
			previous_(NULL),
			next_(NULL)
		{
		}
	};

	template <class K>
	class HashKey
	{
	public:
		static size_t value( const size_t &size, const K &key )
		{
			return ((size_t)key) % size;
		}
	};

	template<class K, class T, class Kfn = HashKey<K> >
	class HashMap
	{
	public:
		typedef HashNode<K, T> Node, *NodePtr;

	private:
		size_t nodeCount_;
		size_t nodeCapacity_;
		size_t bucketCount_;
		int64  conflictCount_;
		int64  conflictCount2_;
		int64  insertCount_;
		HashNode<K, T> **bucketNodes_;
		HashNode<K, T> *lastTopNode_;

	public:
		HashMap()
		{
			nodeCount_      = 0;
			bucketCount_    = 0;
			conflictCount_  = 0;
			conflictCount2_ = 0;
			insertCount_    = 0;
			nodeCapacity_   = 0;
			bucketNodes_    = NULL;
			lastTopNode_    = NULL;
		}

		~HashMap()
		{
			release();
		}

		inline HashNode<K, T> **getBucketNodes(){ return bucketNodes_; }
		inline size_t getNodeCount(){ return nodeCount_; }
		inline size_t getNodeCapacity(){ return nodeCapacity_; }
		inline size_t getBucketCount(){ return bucketCount_; }
		inline int64  getInsertCount(){ return insertCount_; }
		inline int64  getConflictCount(){ return conflictCount_; }
		inline HashNode<K, T> *getLastTopNode(){ return lastTopNode_; }

		//
		// release all items and memories
		// return return value
		//
		void release()
		{
			if( bucketCount_ > 0 )
			{
				removeAll();
				free(bucketNodes_);
			}

			nodeCount_     = 0;
			bucketCount_   = 0;
			conflictCount_ = 0;
			insertCount_   = 0;
			bucketNodes_  = NULL;
			lastTopNode_  = NULL;
		}

		// 
		// initialize hash table with specific bucket size
		// the original items will be released
		// return true if allocate and initialize success, false if not enough memory
		//
		bool initialize( size_t size, size_t nodeCapacity = 0 )
		{
			assert(size > 0 && NULL == bucketNodes_);

			release();

			bucketNodes_ = (HashNode<K, T> **)malloc(sizeof(HashNode<K,T> *) * size);
			bucketCount_  = size;
			nodeCapacity_ = nodeCapacity;

			if( NULL == bucketNodes_ )
			{
				bucketNodes_ = NULL;
				bucketCount_ = 0;
				return false;
			}

			for( size_t n = 0; n < size; n ++ )
			{
				bucketNodes_[n] = NULL;
			}

			return true;
		}

		void _repairRemovedTopNode( HashNode<K, T> *node )
		{
			HashNode<K, T> *previousNode = node->previous_;
			HashNode<K, T> *nextNode = node->next_;
			HashNode<K, T> *childNode = node->child_;

			if( lastTopNode_ == node )
			{
				lastTopNode_ = nextNode ? nextNode : previousNode;
			}

			if( childNode )
			{
				childNode->previous_ = node->previous_;
				childNode->next_ = node->next_;

				if( previousNode ) previousNode->next_ = childNode;
				if( nextNode ) nextNode->previous_ = childNode;
			}
			else
			{
				if( previousNode ) previousNode->next_ = nextNode;
				if( nextNode ) nextNode->previous_ = previousNode;
			}
		}

		//
		// insert new value with key
		// return true if insert success, a new item will be added,
		// false if the key exist or not enough memory to allocate new item
		//
		T *insert( const K &key, const T &value )
		{
			assert(bucketCount_ > 0);

			if( nodeCapacity_ > 0 && nodeCount_ >= nodeCapacity_ )
			{
				return NULL;
			}

			insertCount_ ++;

			size_t nPos = Kfn::value(bucketCount_, key);
			assert(nPos < bucketCount_);

			HashNode<K, T> *lastNode = bucketNodes_[nPos];
			HashNode<K, T> *node = lastNode;
			while( NULL != node )
			{
				if( key == node->key_ )
				{
					// already exist
					return NULL;
				}

				conflictCount_ ++;
				lastNode = node;
				node = lastNode->child_;
			}

			HashNode<K, T> *newNode = new HashNode<K, T>(key, value);
			if( NULL == newNode )
			{
				// allocate failed
				return NULL;
			}

			// attach to tail
			if( NULL == lastNode )
			{
				bucketNodes_[nPos] = newNode;
				if( NULL != lastTopNode_ )
				{
					lastTopNode_->next_ = newNode;
					newNode->previous_ = lastTopNode_;
				}
				lastTopNode_ = newNode;
			}
			else
			{
				lastNode->child_ = newNode;
			}
			nodeCount_ ++;
			return &(newNode->value_);
		}

		//
		// remove item by key
		// return true if key exist, the item will be removed
		// false if not exist
		//
		bool removeKey( const K &key )
		{
			assert(bucketCount_ > 0);

			size_t nPos = Kfn::value(bucketCount_, key);
			assert(nPos < bucketCount_);

			HashNode<K, T> *node = bucketNodes_[nPos];

			// find in the list
			HashNode<K, T> *previousNode = node;
			while( NULL != node && !(key == node->key_) )
			{
				previousNode = node;
				node = node->child_;
			}

			if( NULL == node )
			{
				// not found
				return false;
			}

			// cut and free the found node
			if( previousNode == node )
			{
				_repairRemovedTopNode(node);
				bucketNodes_[nPos] = node->child_;
			}
			else
			{
				previousNode->child_ = node->child_;
			}

			delete node;

			nodeCount_ --;
			return true;
		}

		//
		// remove all items while value is matched
		// return count been cleaned
		//
		size_t removeValue( const T &value )
		{
			size_t removeCount = 0;

			for( size_t n = 0; n < bucketCount_; n ++ )
			{
				HashNode<K, T> *node = bucketNodes_[n];
				HashNode<K, T> *previousNode = node;
				while( NULL != node )
				{
					if( value == node->value_ )
					{
						removeCount ++;
						if( previousNode == node )
						{
							_repairRemovedTopNode(node);
							bucketNodes_[n] = node->child_;
							previousNode = node->child_;

							delete node;
							node = previousNode;
						}
						else
						{
							previousNode->child_ = node->child_;
							delete node;
							node = previousNode->child_;
						}
					}
					else
					{
						previousNode = node;
						node = node->child_;
					}
				}
			}

			nodeCount_ -= removeCount;
			return removeCount;
		}

		//
		// remove strictly by key together with value
		// return true if key and value are matched, the item will be removed,
		// false if key or value not match
		//
		bool remove( const K &key, const T &value )
		{
			assert(bucketCount_ > 0);

			size_t nPos = Kfn::value(bucketCount_, key);
			assert(nPos < bucketCount_);

			HashNode<K, T> *node = bucketNodes_[nPos];

			// find the list
			HashNode<K, T> *previousNode = node;
			while( NULL != node && (key != node->key_ || value != node->value_) )
			{
				previousNode = node;
				node = node->child_;
			}

			if( NULL == node )
			{
				// not found
				return false;
			}

			// cut and free the found node
			if( previousNode == node )
			{
				_repairRemovedTopNode(node);
				bucketNodes_[nPos] = node->child_;
			}
			else
			{
				previousNode->child_ = node->child_;
			}

			delete node;
			nodeCount_ --;
			return true;
		}

		//
		// remove all items
		// return removed count
		//
		size_t removeAll()
		{
			size_t removedCount = 0;
			for( size_t n = 0; n < bucketCount_; n ++ )
			{
				HashNode<K,T> *node = bucketNodes_[n];
				while( NULL != node )
				{
					HashNode<K,T> *freeNode = node;
					node = freeNode->child_;
					delete freeNode;
					removedCount ++;
				}
				bucketNodes_[n] = NULL;
			}
			lastTopNode_ = NULL;
			nodeCount_ = 0;
			return removedCount;
		}

		//
		// find item by key
		// return value's address if key exist,
		// NULL if key not exist
		//
		T *find( const K &key ) const
		{
			assert(bucketCount_ > 0);

			size_t pos = Kfn::value(bucketCount_, key);
			assert(pos < bucketCount_);

			HashNode<K, T> *node = bucketNodes_[pos];
			while( NULL != node && !(key == node->key_) )
			{
				node = node->child_;
			}

			return (NULL == node) ? NULL : &(node->value_);
		}

		// 
		// find item by key
		// return true if key exist and value is set to the item value,
		// false if not exist and value will not changed
		//
		bool find( const K &key, T &value ) const
		{
			T *valuePtr = find(key);
			if( NULL == valuePtr )
			{
				return false;
			}

			value = *valuePtr;
			return true;
		}

		//
		// test is key is exist
		// return true if key is exist, else false
		//
		bool isExists( const K &key ) const
		{
			assert(bucketCount_ > 0);

			size_t pos = Kfn::value(bucketCount_, key);
			assert(pos < bucketCount_);

			HashNode<K, T> *node = bucketNodes_[pos];
			while( NULL != node && !(key == node->key_) )
			{
				node = node->child_;
			}

			return (NULL != node);
		}
	};

	template<class K, class T, class Kfn = HashKey<K> >
	class MemHashMap
	{
	public:
		typedef HashNode<K, T> Node, *NodePtr;

	private:
		size_t nodeCount_;
		size_t bucketCount_;
		size_t conflictCount_;
		size_t conflictCount2_;
		size_t insertCount_;
		bool *bucketUsed_;
		HashNode<K, T> *bucketNodes_;

		inline void deleteHeadNode( const size_t &pos )
		{
			HashNode<K, T> *node = bucketNodes_ + pos;

			if( NULL == node->child_ )
			{
				// mark unused
				bucketUsed_[pos] = false;
			}
			else
			{
				// switch content with the next node
				// then free the next node
				HashNode<K, T> *freeNode = node->child_;

				node->key_   = freeNode->key_;
				node->value_ = freeNode->value_;
				node->child_ = freeNode->child_;

				free(freeNode);
			}
		}

	public:
		MemHashMap()
		{
			nodeCount_ = 0;
			bucketCount_ = 0;
			conflictCount_  = 0;
			conflictCount2_ = 0;
			insertCount_    = 0;
			bucketUsed_ = NULL;
			bucketNodes_ = NULL;
		}

		~MemHashMap()
		{
			release();
		}

		inline HashNode<K, T> *getBucketNodes(){ return bucketNodes_; }
		inline bool *getBucketUsedFlags(){ return bucketUsed_; }
		inline size_t getCount(){ return nodeCount_; }
		inline size_t getBucketCount(){ return bucketCount_; }
		inline size_t getInsertCount(){ return insertCount_; }
		inline size_t getConflictCount(){ return conflictCount_; }
		inline size_t getConflictCount2(){ return conflictCount2_; }

		//
		// release all items and memories
		// return return value
		//
		void release()
		{
			if( bucketCount_ > 0 )
			{
				removeAll();
				free(bucketNodes_);
				free(bucketUsed_);
			}

			nodeCount_ = 0;
			bucketCount_ = 0;
			conflictCount_ = 0;
			insertCount_   = 0;
			bucketNodes_ = NULL;
			bucketUsed_ = NULL;
		}

		// 
		// initialize hash table with specific bucket size
		// the original items will be released
		// return true if allocate and initialize success, false if not enough memory
		//
		bool initialize( size_t size )
		{
			assert(size > 0 );

			release();
			
			bucketNodes_ = (HashNode<K, T> *)malloc(sizeof(HashNode<K,T>) * size);
			bucketUsed_ = (bool *)malloc(sizeof(bool) * size);
			bucketCount_ = size;

			if( NULL == bucketNodes_ || NULL == bucketUsed_ )
			{
				if( NULL != bucketNodes_ ) free(bucketNodes_);
				if( NULL != bucketUsed_ ) free(bucketUsed_);

				bucketNodes_ = NULL;
				bucketUsed_ = NULL;
				bucketCount_ = 0;

				return false;
			}

			for( size_t n = 0; n < size; n ++ )
			{
				bucketNodes_[n].child_ = NULL;
				bucketUsed_[n] = false;
			}

			return true;
		}

		//
		// insert new value with key
		// return true if insert success, a new item will be added,
		// false if the key exist or not enough memory to allocate new item
		//
		bool insert( const K &key, const T &value, bool replaceIfExists )
		{
			assert(bucketCount_ > 0);

			insertCount_ ++;

			size_t pos = Kfn::value(bucketCount_, key);
			assert(pos < bucketCount_);

			if( !bucketUsed_[pos] )
			{
				HashNode<K, T> *node = &(bucketNodes_[pos]);
				bucketUsed_[pos] = true;
				node->key_ = key;
				node->value_ = value;
				node->child_ = NULL;
				nodeCount_ ++;
				return true;
			}

			HashNode<K, T> *lastNode = &(bucketNodes_[pos]);
			HashNode<K, T> *node = lastNode;
			while( NULL != node )
			{
				if( key == node->key_ )
				{
					// already exist
					if( !replaceIfExists )
					{
						return false;
					}
					node->value_ = value;
					return false;
				}
				conflictCount2_ ++;
				lastNode = node;
				node = lastNode->child_;
			}
			conflictCount_ ++;

			// for speed up, not use try,catch
			HashNode<K, T> *newNode = (HashNode<K, T> *)malloc(sizeof(HashNode<K, T>));
			if( NULL == newNode )
			{
				// allocate failed
				return false;
			}

			newNode->key_   = key;
			newNode->value_ = value;
			newNode->child_  = NULL;

			// attach to tail
			lastNode->child_ = newNode;
			nodeCount_ ++;
			return true;
		}

		//
		// remove item by key
		// return true if key exist, the item will be removed
		// false if not exist
		//
		bool remove( const K &key )
		{
			assert(bucketCount_ > 0);

			size_t pos = Kfn::value(bucketCount_, key);
			assert(pos < bucketCount_);
			
			if( !bucketUsed_[pos] )
			{
				return false;
			}

			HashNode<K, T> *node = &(bucketNodes_[pos]);

			// is the first node ?
			if( key == node->key_ )
			{
				deleteHeadNode(pos);
				nodeCount_ --;
				return true;
			}
			
			// find in the list
			HashNode<K, T> *previousNode = node;

			node = node->child_;
			while( NULL != node && !(key == node->key_) )
			{
				previousNode = node;
				node = node->child_;
			}

			if( NULL == node )
			{
				// not found
				return false;
			}

			// cut and free the found node
			previousNode->child_ = node->child_;
			free(node);

			nodeCount_ --;
			return true;
		}

		//
		// remove strictly by key together with value
		// return true if key and value are matched, the item will be removed,
		// false if key or value not match
		//
		bool remove( const K &key, const T &value )
		{
			assert(bucketCount_ > 0);

			size_t pos = Kfn::value(bucketCount_, key);
			assert(pos < bucketCount_);

			if( !bucketUsed_[pos] )
			{
				return false;
			}

			HashNode<K, T> *node = &(bucketNodes_[pos]);

			// is the first node ?
			if( key == node->key_ && value == node->value_ )
			{
				deleteHeadNode(pos);
				nodeCount_ --;
				return true;
			}

			// find the list
			HashNode<K, T> *previousNode = node;

			node = node->child_;
			while( NULL != node && (!(key == node->key_) || !(value == node->value_)) )
			{
				previousNode = node;
				node = node->child_;
			}

			if( NULL == node )
			{
				// not found
				return false;
			}

			// cut and free the found node
			previousNode->child_ = node->child_;
			free(node);

			nodeCount_ --;
			return true;
		}

		//
		// clean all items while value is matched
		// return count been cleaned
		//
		size_t clean( const T &value )
		{
			size_t removeCount = 0;

			for( size_t n = 0; n < bucketCount_; n ++ )
			{
				if( !bucketUsed_[n] )
				{
					// empty node
					continue;
				}

				HashNode<K, T> *node = &(bucketNodes_[n]);
				while( bucketUsed_[n] && value == node->value_ )
				{
					removeCount ++;
					deleteHeadNode(n);
				}

				if( !bucketUsed_[n] )
				{
					// cleaned
					continue;
				}

				HashNode<K, T> *previousNode = node;
				node = node->child_;
				while( NULL != node )
				{
					if( value == node->value_ )
					{
						removeCount ++;

						previousNode->child_ = node->child_;
						free(node);
						node = previousNode->child_;
					}
					else
					{
						previousNode = node;
						node = node->child_;
					}
				}
			}

			nodeCount_ -= removeCount;
			return removeCount;
		}

		//
		// remove all items
		// return removed count
		//
		size_t removeAll()
		{
			assert(NULL != bucketNodes_);
			assert(NULL != bucketUsed_);

			size_t removedCount = 0;
			for( size_t n = 0; n < bucketCount_; n ++ )
			{
				if( !bucketUsed_[n] )
				{
					continue;
				}

				HashNode<K,T> *node = bucketNodes_[n].child_;
				while( NULL != node )
				{
					HashNode<K,T> *pFreeNode = node;
					node = pFreeNode->child_;
					free(pFreeNode);
					removedCount ++;
				}
				if( bucketUsed_[n] ) removedCount ++;
				bucketNodes_[n].child_ = NULL;
				bucketUsed_[n] = false;
			}

			return removedCount;
		}

		//
		// find item by key
		// return value's address if key exist,
		// NULL if key not exist
		//
		T *find( const K &nKey ) const
		{
			assert(bucketCount_ > 0);

			size_t pos = Kfn::value(bucketCount_, nKey);
			assert(pos < bucketCount_);

			if( !bucketUsed_[pos] )
			{
				return NULL;
			}

			HashNode<K, T> *node = &(bucketNodes_[pos]);
			while( NULL != node && !(nKey == node->key_) )
			{
				node = node->child_;
			}

			return (NULL == node) ? NULL : &(node->value_);
		}

		// 
		// find item by key
		// return true if key exist and value is set to the item value,
        // false if not exist and value will not changed
		//
		bool find( const K &key, T &value ) const
		{
			T *valuePtr = find(key);
			if( NULL == valuePtr )
			{
				return false;
			}

			value = *valuePtr;
			return true;
		}

		//
		// test is key is exist
		// return true if key is exist, else false
		//
		bool isExists( const K &key ) const
		{
			assert(bucketCount_ > 0);

			size_t pos = Kfn::value(bucketCount_, key);
			assert(pos < bucketCount_);

			if( !bucketUsed_[pos] )
			{
				return false;
			}

			HashNode<K, T> *node = &(bucketNodes_[pos]);
			while( NULL != node && !(key == node->key_) )
			{
				node = node->child_;
			}

			return (NULL != node);
		}
	};
}}

#endif //__CORE_COMMON_HASH_MAP_H_INCLUDE__
